#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <cstring>
using namespace std;
typedef pair<int, int> pii;

#define MAXN 100+5
#define INF 0x3F3F3F3F

vector<pii> G[MAXN];

int N, M;
int dis[MAXN];
bool vis[MAXN];

void input() {
	for (int i=1; i<=N; i++) {
		G[i] = vector<pii>();
	}
	for (int i=1; i<=M; i++) {
		int A, B, C;
		scanf("%d%d%d", &A, &B, &C);
		G[A].push_back(make_pair(B, C));
		G[B].push_back(make_pair(A, C));
	}
}

int SPFA() {
	queue<int> q;
	memset(dis, 0x3F, sizeof(dis));
	dis[1] = 0;
	memset(vis, 0, sizeof(vis));
	q.push(1);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		//if (vis[u]) continue;
		vis[u] = true;
		for (vector<pii>::iterator it = G[u].begin(); it != G[u].end(); it++) {
			int v = it->first;
			int c = it->second;
			if (dis[v] > dis[u]+c) {
				dis[v] = dis[u]+c;
				q.push(v);
			}
		}
		vis[u] = false;
	}
	return dis[N];
}

int main() {
	while (true) {
		scanf("%d%d", &N, &M);
		if (N==0 && M==0) break;
		input();
		int result = SPFA();
		printf("%d\n", result);	
	}
	return 0;
}
